//二叉排序树

#pragma once

//二叉排序树类型定义
template<typename E>
 struct BSTNode
 {
   E data;
   BSTNode *lchild,  *rchild;
 };

 template<typename E>
 using BSTree=BSTNode<E>*;

 //二叉排序树的算法

 //最小元素
 //若找到，则返回指向最小元素结点的指针20 
 //否则，返回空指针
 template<typename E>
 BSTree<E> FindMin(BSTree<E> T)
{
 if(T==nullptr)
 return nullptr;

 auto p=T;
 while(p->lchild)
 p=p->lchild;
    return p;
}
//最大元素
template<typename E>
BSTree<E> FindMax(BSTree<E> T)
{
    if(T==nullptr)
 return nullptr;

 auto p=T;
 while(p->rchild)
 p=p->rchild;
 return p;
}

//在二叉排序T中查找元素e
//若找到，返回指向该结点的指针
//否则，返回空指针
 template<typename E>
    BSTree<E> SearchBST(BSTree<E>T, E e)
    {
    if(T==nullptr)
      return nullptr;
    if(T->data==e)
      return T;
    else if(e<T->data)
      return SearchBST(T->lchild, e) ;
    else
      return SearchBST(T->rchild, e);
    }

    //查找元素(非递归算法)
    template <typename E>
    BSTree<E> Search(BSTree<E>T, E e)
    {
        auto p = T;
        while(p && p->data != e)
        {
          p=(e<p->data) ?p->lchild:p->rchild;
          //if (e<p->data)
          //p=p->lchild;
          //else
          //p=p->rchild;
        }
    
        return p;
    }

  
//插入元素(递归算法)
//在二叉排序树T中入数据元素e
//若元素e已经存在，则不再插入
//返回e所在结点的指针
template<typename E>
BSTree<E> InsertBST(BSTree<E> &T, E e)
  {
   //若二又树为空，则
   if(T==nullptr) {  //二叉树为空
      T=new BSTNode<E>{e, nullptr,nullptr}; //插入结点作为检结点
      return T;
   }
    else if(e < T->data)                     //待插入元素e小于结点
       return InsertBST(T->lchild, e) ;      //继续在左子树上插入
    else if(e>T->data)                       //待插入元素e大于检结点
       return InsertBST(T->rchild, e) ;      //继续在右子树上插入
    else                                     //若待赫入元素e等于检结点97 return T；
       return T;                             //直接返回检结点 
  }

//插入元素(非递归算法)
template <typename E>
BSTree<E> Insert(BSTree<E> &T,E e)
{
  //查找元素e及其双亲f
  BSTree<E>p, f;
  p = T, f = nullptr;
  while(p&&p->data!=e)
    if (e<p->data) {
      f=p; p=p->lchild;
    } else{
      f=p; p=p->rchild;
    }

  //若找到e，则直接返回
  if(p)
     return p;

  //否则未找到e，则插入新结点作为f的孩子
  auto s = new BSTNode<E> (e, nullptr, nullptr);
  if(f == nullptr) //T为空
     T = s;//新结点作为检结点
  else if(e < f->data)
    f->lchild=s; //s作为f的左孩子
  else
    f->rchild=s; //s作为f的右孩子
  return s; //返回新建结点s
}

//附除元素(递归算法)
//在二叉排序树T中州除元素e所在的结点
//若元素e不存在， 则不做任何操作， 返回false
//最后， 若删除成功则返回true
template <typename E>
bool DeleteBST(BSTree<E> &T, E e)
{
  //递归停止条件：二叉树为空， 返回false
  if(T==nullptr)  return false;
  //若e在T的左子树，则缝续在左子树附除
  else if(e < T->data) return DeleteBST(T->lchild, e) ;
  //若e在T的右子树，在缝续在右子树附除
  else if(e>T->data) return DeleteBST(T->rchild, e) ;
  //e等于检结点T->data， 则附除T(分情况：左右子树均不空， 至少有一个子树为空)
  //若T的左右子树均不空
  else if(T->lchild&&T->rchild) {
  //用T的左子树上最大元素， 替焕T->data
    T->data=FindMax(T->lchild) ->data;
    //在T的左子树上删除该最大元素
    return DeleteBST(T->lchild, T->data);
  }
  //T的左右子树至少有一个为空
  else{
    auto p=T; //待附除的结点
    T = T->lchild ? T->lchild:T->rchild;
    delete p;
    return true;
  }
}